The incidence of malignant melanoma continues to increase, while no treatment other than early surgical excision is of proven benefit. Among experimental adjuvant treatment approaches, active specific immunotherapy is the most promising. Previous Phase I and II studies with vaccinia melanoma oncolysate (VMO) have established the safety of this approach and the immunogenicity of VMO. This proposed study consists of a multi-institutional, randomized, prospective double-blind Phase III trial of Vaccinia to determine the effect of VMO treatment of disease-free survival of early stage high risk melanoma. One hundred and ninety-two patients who present with stage II melanoma who are clinically free from disease after surgery, but at high risk for recurrence, will be randomized to receive either VMO or vaccinia. Following pretreatment testing and an initial smallpox booster, patients will receive weekly injections of coded inoculum (lml containing either VMO or vaccinia) intradermally for 13 weeks followed by injections every 2 weeks up to 12 months or until recurrence. Serologic monitoring to detect anti-melanoma and anti-vaccinia antibodies will be performed at Mount Sinai on sera obtained before treatment and at monthly intervals during treatment using ELISA assays. Multi-test skin testing will be performed pretreatment and at 6 months. At the end of the study the treatment code will be broken and immune response data and disease-free survival data obtained from the VMO treatment group vs. the vaccinia group will be compared. The results of this trial should provide definitive information concerning the efficacy of VMO and the prognostic significance of anti-melanoma antibody production during treatment.